//
// Created by Administrator on 2024/4/9.
//
#include<bits/stdc++.h>

using namespace std;

int fx[][2] = {0, 1, 0, -1, 1, 0, -1, 0}; //4-directions array
int main() {
    int n = 5, m = 5, sx = 0, sy = 0, ex = n - 1, ey = m - 1;
    vector<vector<int>> maze(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> maze[i][j];
        }
    }
    vector<vector<int>> book(n, vector<int>(m, 0));
    vector<vector<pair<int, int>>> pre(n, vector<pair<int, int>>(m, make_pair(-1, -1)));//previous matrix
    queue<pair<int, int>> q;
    q.push(make_pair(sx, sy));
    book[sx][sy] = 1;
    pre[sx][sy] = make_pair(-1, -1); //(sx,sy) is root of bfs_search_tree
    int cnt = 0;
    while (!q.empty()) {
        auto head = q.front();
        int hx = head.first;
        int hy = head.second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = hx + fx[i][0];
            int ny = hy + fx[i][1];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || maze[nx][ny] == 1 || book[nx][ny] == 1)continue;
            q.push(make_pair(nx, ny));
            book[nx][ny] = 1;
            pre[nx][ny] = make_pair(hx, hy);
        }
    }
    stack<pair<int, int>> trace;//shortest_path  from end_point(ex,ey) to start_point(sx,sy)
    trace.push(make_pair(ex, ey));
    while (true) {
        int tx = trace.top().first;
        int ty = trace.top().second;
        if (tx == sx && ty == sy)break;
        trace.push(pre[tx][ty]);
    }
    while (!trace.empty()) {
        cout << "(" << trace.top().first << "," << trace.top().second << ")" << endl;
        trace.pop();
    }

    return 0;
}